package cn.zifangsky.tree.binarytree.questions;

import org.junit.Test;

import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.tree.binarytree.BinaryTreeNode;

/**
 * 实现将一棵树转换为其镜像的算法
 * 树的镜像：指交换非叶子节点的节点的左子树和右子树
 * @author zifangsky
 *
 */
public class Question15 {

	/**
	 * 将一棵树转换为其镜像
	 * 
	 * @时间复杂度 O(n)
	 * @param root
	 * @return
	 */
	public BinaryTreeNode<Integer> mirrorOfTree(BinaryTreeNode<Integer> root){
		//如果当前节点不为空，且不是叶子节点，则交换其左子树和右子树
		if(root != null && !(root.getLeft() == null && root.getRight() == null)){
			BinaryTreeNode<Integer> tempNode = root.getLeft(); //临时变量
			root.setLeft(root.getRight());
			root.setRight(tempNode);
			
			mirrorOfTree(root.getLeft()); //继续递归处理当前的左子树
			mirrorOfTree(root.getRight()); //继续递归处理当前的右子树
		}
		return root;
	}

	/**
	 * 前序遍历
	 * @时间复杂度 O(n)
	 * @param root
	 */
	private void preOrder(BinaryTreeNode<Integer> root){
		if(root != null){
			System.out.print(root.getData() + " ");
			preOrder(root.getLeft()); //遍历左子树
			preOrder(root.getRight()); //遍历右子树
		}
	}

	/**
	 * 测试用例
	 */
	@Test
	public void testMethods(){
		/**
		 * 使用队列构造一个供测试使用的二叉树
		 *     1
		 *   2    3
		 * 4  5  6  7
		 *   8 9  
		 */
		LinkQueue<BinaryTreeNode<Integer>> queue = new LinkQueue<BinaryTreeNode<Integer>>();
		BinaryTreeNode<Integer> root = new BinaryTreeNode<>(1); //根节点
		
		queue.push(root);
		BinaryTreeNode<Integer> temp = null;
		for(int i=2;i<10;i=i+2){
			BinaryTreeNode<Integer> tmpNode1 = new BinaryTreeNode<>(i);
			BinaryTreeNode<Integer> tmpNode2 = new BinaryTreeNode<>(i+1);
			
			temp = queue.pop();
			
			temp.setLeft(tmpNode1);
			temp.setRight(tmpNode2);
			
			if(i != 4)
				queue.push(tmpNode1);
			queue.push(tmpNode2);
		}

		mirrorOfTree(root);
		
		System.out.println("该镜像树的前序遍历结果是：");
		preOrder(root);
	}

}
